package week_01;

public class MergeSortedArray_88 {

    public static void main(String[] args) {

        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int m = 3;
        int[] nums2 = {2, 5, 6};
        int n = 3;
        MergeSortedArray_88 soultion = new MergeSortedArray_88();
        soultion.merge(nums1, m, nums2, n);
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 从后往前算，谁大要谁
        // i，j 都不能越界 <0
        int i = m - 1;
        int j = n - 1;
        // k 是插入位置
        for (int k = m + n - 1; k >= 0; k--) {
            if (j < 0 || (i >= 0) && nums1[i] >= nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                // 其他情况：i<0 或者 nums[i]<nums2[j]
                nums1[k] = nums2[j];
                j--;
            }
        }

    }

    /**
     * 从头开始换，往后挪为小数腾位置
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int d = 0;
        int k = 0;
        while (d < nums1.length) {
            if (k < n && (nums2[k] < nums1[d])) {
                for (int i = m; i > d; i--) {
                    nums1[i] = nums1[i - 1];
                }
                nums1[d] = nums2[k];
                k++;
                m = m + 1;
            } else if (k < n && d >= m) {
                nums1[d] = nums2[k];
                k++;
            }
            d++;
        }

    }

    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        int[] ans = new int[nums1.length];
        int idx1 = 0;
        int idx2 = 0;
        int idx = 0;
        while (m > idx1 && n > idx2) {
            if (nums1[idx1] <= nums2[idx2]) {
                ans[idx] = nums1[idx1];
                idx1++;
            } else {
                ans[idx] = nums2[idx2];
                idx2++;
            }
            idx++;
        }

        while (idx1 < m) {
            ans[idx] = nums1[idx1];
            idx++;
            idx1++;
        }


        while (idx2 < n) {
            ans[idx] = nums2[idx2];
            idx++;
            idx2++;
        }
        for (int i = 0; i < nums1.length; i++) {
            nums1[i] = ans[i];
        }

    }
}
